\documentclass[10pt,pdf,hyperref={unicode}]{beamer}
\usepackage[T2A]{fontenc}       %поддержка кириллицы
%\usepackage[koi8-r]{inputenc}   %пока бибтех не дружит до конца с юникодом
\usepackage[utf8]{inputenc}
\usepackage[russian, english]{babel}     %определение языков в документе
\usepackage{amssymb,amsmath}    %математика

%\graphicspath{{./pictures/}{../../pictures/}} %относительный путь к
                                %каталогу с рисунками (обязателен слеш
                                %в конце!)
\graphicspath{{./img/}}

% Тема презентации
\usetheme[numbers, totalnumbers, minimal, nologo]{Statmod}

%%%%%%%%%%%%%%%%%%%
%% Выбор шрифтов %%
\usefonttheme[onlylarge]{structurebold}

% Привычный шрифт для математических формул
\usefonttheme[onlymath]{serif}

% Более крупный шрифт для подзаголовков титульного листа
\setbeamerfont{institute}{size=\normalsize}
%%%%%%%%%%%%%%%%%%%

% Если используется последовательное появление пунктов списков на
% слайде (не злоупотребляйте в слайдах для защиты дипломной работы),
% чтобы еще непоявившиеся пункты были все-таки немножко видны.
\setbeamercovered{transparent}

%%%%%%%%%%%%%%%%%%
%%% Сокращения %%%
% Синий цвет выделения
\setbeamercolor{color1}{bg=blue!60!black,fg=white}
%%%%%%%%%%%%%%%%%%

\title[Обработка графа де Брюина]{Разработка алгоритмов обработки графа де Брюина в задаче геномного ассемблирования}
%\shorttitle{Орбаботка графов де Брюина}
\author{Нурк Сергей Юрьевич, 545 гр.}
\institute{Кафедра системного программирования \\
    \vspace{0.7cm}
    Научный руководитель: Н. Вяххи \\
    \vspace{0.7cm}
    Рецензент: М. Алексеев \\
    \vspace{0.7cm}
}
\date{
    Мат-Мех СПбГУ\\
    23 мая 2011г.
}

\begin{document}
\begin{frame}
  % создаём титульный лист
  \maketitle
\end{frame}

\begin{frame}
\frametitle{Геном и секвенирование}

\begin{itemize}
\item Геном --- полная наследственная информация об организме
\item Закодирован в ДНК. Длинная строка, алфавит из 4 букв (A,T,G,C)
\item Длина генома \textit{E.coli} $4.5$ млн. букв, человека --- $3.2$ млрд. букв
\item Секвенирование --- процесс определения генома
\begin{itemize}
\item Стоимость: $10$ тысяч долларов
\item Время: $4$ дня
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Входные данные, ассемблирование}
\begin{columns}
\column{0.5\textwidth}
\begin{itemize}
\item Входные данные:
\begin{itemize}
\item Короткие фрагменты ($100-200$ нуклеотидов)
\item Фрагменты идут парами c фиксированным расстоянием внутри пары ($20-1000$)
\item Ошибки во фрагментах и расстоянии между ними.
\end{itemize}
\item Ассемблирование --- восстановление (вычисление) исходной последовательности из фрагментов
\end{itemize}

\column{0.5\textwidth}
\includegraphics[width=\columnwidth]{sequencing}    	
\end{columns}
\end{frame}

\begin{frame}
\frametitle{Граф повторов}
\includegraphics[width=\textwidth]{repeat_graph_def2}
\end{frame}	

\begin{frame}
\frametitle{Граф де Брюина}
  \begin{columns}
    \column{0.5\textwidth}
    Граф повторов
	\includegraphics[width=\columnwidth]{repeat_graph}    	
    \column{0.5\textwidth}
    \only<1>{
	    Граф де Брюина, построенный по фрагментам
		\includegraphics[width=\columnwidth]{de_bruijn}    	
    }
    \only<2>{
	    Упрощенный граф де Брюина
		\includegraphics[width=\columnwidth]{approx}    	
    }
  \end{columns}
  \vspace{0.5cm}
\end{frame}	

\begin{frame}
\frametitle{Основные цели работы}
\begin{block}{}
\begin{itemize}
\item<1-> Спроектировать архитектуру для быстрого создания алгоритмов обработки графа.
\item<2-> Разработать алгоритмы устранения ошибочных участков графа.
\end{itemize}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Ошибочные участки графа}
%Ошибки в исходных фрагментах приводят к появлению:
\begin{columns}
    \column{0.3\textwidth}
	\begin{itemize}
	\item<2-> Тупики
	\item<3-> Пузыри
	\item<4-> Ошибочные соединения
	\end{itemize}
	\column{0.7\textwidth}
    \only<1,5>{
		\includegraphics[width=\columnwidth]{fewer_errors_de_bruijn}    	
    }
    \only<2>{
		\includegraphics[width=\columnwidth]{tips_de_bruijn}    	
    }

    \only<3>{
		\includegraphics[width=\columnwidth]{bulges_de_bruijn}    	
    }
    \only<4>{
		\includegraphics[width=\columnwidth]{erroneous_de_bruijn}    	
    }
\end{columns}

\only<5>{Для каждого из перечисленных типов участков разработан свой алгоритм.}
%Трудность: аналогичные структуры присутствуют и в безошибочном графе.
\end{frame}

\begin{frame}
\frametitle{Особенности нашего подхода}
Дополнительная информация на графе:
\begin{itemize}
\item Покрытие ребер
\item Межреберные расстояния
\end{itemize}

\begin{block}{}
Мы поддерживаем и активно используем эту информацию в процессе обработки графа.% и что??? что оно позволило сделать-то???
%Необходима и на последующих шагах, мы используем ее при устранении ошибок.
\end{block}
\end{frame}

\begin{frame}
\frametitle{Итоги}

\begin{itemize}
\item Разработан алгоритм построения графа де Брюина.
\item Спроектированная архитектура позволяет быстро разрабатывать новые алгоритмы обработки графа.
\item Разработаны алгоритмы устранения всех основных ошибочных участков графа, допускающие тонкую настройку.
\item Разработаны новые методы поддержания и использования дополнительной информации.
\item Система разрабатывается на C++ в рамках проекта лаборатории алгоритмической биологии СПбАУ РАН.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Экспериментальные результаты}
E.coli, 14 млн. парных фрагментов
\begin{itemize}
\item Время работы: 40 мин
\item Пиковые затраты памяти: 1 Gb
\item До упрощений: 30 тыс. вершин 35 тыс. ребер
\item После упрощений остается 6.5 тыс вершин и 9.8 тыс ребер
\end{itemize}
\end{frame}

\end{document}
